1. Field of the Invention
The present invention concerns a coding method and device, a decoding method and device, and equipment using them. In particular the invention aims to generate code words belonging to a Reed-Solomon code on a Galois field having q elements, the code words generated having all their symbols in a sub-alphabet of this Galois field.
2. Description of the Background
This method is Particularly applied to Reed-Solomon codes on a 256-element Galois field and a sub-alphabet of this field having 64 elements.
Maximum distance separable codes constitute a particularly interesting family of error correction codes. These codes are defined on an alphabet F provided with a Galois field structure GF(q) where q is a power of a prime number p.
Like all linear codes, maximum distance separable codes can be defined by a generator matrix or a control matrix. Known constructions for such matrices effectively corresponding to maximum distance separable codes are the so-called Vandermonde construction or that of Cauchy [Mac Williams and Sloane].
The actual use of a code requires the use of a coder, that is to say a device which, for a code of type (n,k), maps, to each k-tuple of units of information u=(u1, . . . , uk on GF(q), a coded n-tuple v=(v1, . . . , vn), referred to as a xe2x80x9ccoded wordxe2x80x9d, which represents and which is transmitted in its place. From this point of view, a distinction: between systematic coders and non-systematic coders is established. A coder is referred to as systematic if the k components u1 of u appear unmodified as a component vj(l) of the coded word v representing u.
It should be noted that if kxe2x89xa74 or kxe2x89xa6nxe2x88x924, maximum distance separable codes on GF(q) are known only for nxe2x89xa7q+1, and that the case n=qxe2x88x921 is of particular interest. There are, on the electronic component market, many decoders decoding maximum distance separable codes and operating on an alphabet with 256 elements, each of these elements being identified with a different binary octet, and the said alphabet being structured as the Galois field having 256 elements and often denoted GF(256).
For the remote transmission of information, quadrature amplitude modulations allow a high transmission rate. These modulations have, for example, a 64-signal constellation, such that each of the two components carried by the phase quadrature amplitudes can take eight different values. The natural alphabet associated with this type of modulation therefore has 64 elements.
Persons skilled in the art who wish to use 64-element quadrature amplitude modulation are first of all tempted to use a Reed-Solomon code defined on a 64-element Galois field. However the number of symbols in the code words is limited to 65, which may be too low for certain applications.
A code known to persons skilled in the art under the name BCH defined on the 64-element Galois field can also be used. However, this implies that the decoder works on an alphabet with 212=4096 elements, which is not implemented in a conventional technology. Furthermore, for a given correction capability, the redundancy is then most often close to twice what it is in the case of Reed-Solomon codes, since on GF(64), x4095xe2x88x921 factorises into the product of 63 first degree polynomials and 2016 irreducible second degree polynomials.
The present invention intends notably to specify a systematic procedure for encoding sequences of binary information such that the words of the code are words of a maximum distance separable code on the 256-element Galois field, referred to as the xe2x80x9csecond alphabetxe2x80x9d, and, in addition, satisfy the condition that only 64 of the 256 symbols of this alphabet can be used, both as redundant symbols and as information symbols. The 64 symbols of the second alphabet which are used in this way are called the xe2x80x9cfirst alphabetxe2x80x9d.
Thus the decoder can be implemented with a commercial component already produced, at the date of the invention, in large quantities and, consequently, of low cost, while using a transmission channel with quadrature amplitude modulations having 64 elements.
For a given correction capability, the redundancy necessary will then be equal to four thirds of that necessary with a Reed-Solomon code using a 256-element alphabet.
The document EP-0 290 349 (Weng Lih-Jih) is known. In this, given a 256-element sub-alphabet of a 1024-element Galois field, each unit of information to be encoded is represented by k-l symbols of the sub-alphabet to which l arbitrary units of pseudo-information are added, testing the sequences of l arbitrary units of information until the code words contain only symbols of the sub-alphabet, the number l being chosen with the aim that at least one such sequence gives the result sought.
The aim of this document EP-0 290 349 is to keep an octet format for the information and the redundancies, and to construct efficient error correction codes with little redundancy, for encoding long sequences of information.
The document EP-0 290 349 has many drawbacks: it does not suggest using a decoder working on a 256-element Galois field, determination of the units of pseudo-information is not optimised, the number of these units of pseudo-information is not known when the search for them is started, and the said search is empirical and based on a series of tests and checks. The successive test procedures to be used for determining the sequence of l units of pseudo-information are lengthy and they therefore do not allow rapid encoding of the information. Another embodiment disclosed by the document EP-0 290 349 presents the use of a look-up table, which implies the use of a read-only memory whose capacity, at the date of the present invention, is impracticable except for very small values of redundancy.
The invention intends to remedy these drawbacks by proposing, in a single step, to determine a code work all the symbols of which belong to a 64-element sub-alphabet.
This procedure can be matched with the article xe2x80x9cCodes between BCH and RS codesxe2x80x9d, Ch. Couvreur an, Ph. Piret, from the PHILIPS JOURNAL OF RESEARCH nxc2x0. 39, pages 195-205, published in 1984. In this article, codes of determined dimension satisfying the same constraints were suggested within the context of unequal error protection, that is to say within the context of a technical problem with no relation with the present invention.
To that end, the invention relates, according to a first aspect, to a coding device supplying code words, the symbols of which are capable of modulating a physical quantity on a transmission channel making use of symbols of a first alphabet, the decoding of these code words using symbols of a second alphabet containing the first alphabet, the cardinal of the second alphabet being strictly greater than that of the first alphabet and not being an integer power of the cardinal of the first alphabet, a device characterised in that it has:
an input of xe2x80x9cprimaryxe2x80x9d symbols belonging to the first alphabet;
processing means adapted to:
determine redundant symbols capable of allowing decoding of the code words composed of primary symbols and redundant symbols, by a decoder working on the second alphabet;
solve a system of equations expressing the constraints to be met so that the said redundant symbols are in the first alphabet.
an output of the symbols of the code words.
Correlatively, the present invention relates, according to a second aspect, to a coding method supplying code words, the symbols of which are capable of modulating a physical quantity on a transmission channel making use of symbols of a first alphabet, the decoding of these code words using symbols of a second alphabet containing the first alphabet, the cardinal of the second alphabet being strictly greater than that of the first alphabet and not being an integer power of the cardinal of the first alphabet, a method characterised in that it has:
a step of inputting xe2x80x9cprimaryxe2x80x9d symbols belonging to the first alphabet;
a step of determining redundant symbols capable of allowing decoding of the code words formed from primary symbols and redundant symbols, by a decoder working on a second alphabet including the first alphabet and symbols not belonging to the first alphabet having an operation of solving a system of equations expressing the constraints to be met so that the redundant symbols are in the first alphabet;
a step of outputting the symbols of the code words.
According to a third aspect, the invention relates to a coding device supplying code words, the symbols of which are capable of modulating a physical quantity on a transmission channel making use of symbols of a first alphabet, the decoding of these code words using symbols of a second alphabet containing the first alphabet, the cardinal A2 of the second alphabet being strictly greater than the cardinal A1 of the first alphabet and not being an integer power of A1, both A1 and A2 being powers of 2, a device characterised in that it has:
an input of xe2x80x9cprimaryxe2x80x9d symbols belonging to the first alphabet;
processing means adapted to replace part of the primary symbols by symbols representative of these primary symbols, the said part containing a number of bits equal to
[c. Log2 (A1)xe2x88x92r]. Log2 (A2),
xe2x80x83where:
c is the number of cyclotomic classes where there exist roots of the code over the second alphabet, and
r is the number of such roots,
and determine redundant symbols capable of allowing decoding of the code words formed from primary symbols and redundant symbols, by a decoder working on the second alphabet by solving a system of equations expressing the constraints to be met so that the said redundant symbols are in the first alphabet, and
an output of the symbols of the code words.
According to a fourth aspect, the present invention relates to a coding method supplying code words, the symbols of which are capable of modulating a physical quantity on transmission channel making use of symbols of a first alphabet, the decoding of these code words using symbols of a second alphabet containing the first alphabet, the cardinal A2 of the second alphabet being strictly greater than the cardinal A1 of the first alphabet and not being an integer power of A1, both A1 and A2 being powers of 2, a method characterised in that it has:
an step of inputting xe2x80x9cprimaryxe2x80x9d symbols belonging to the first alphabet;
a step of replacing part of the primary symbols by symbols representative of these primary symbols, the said part containing a number of bits equal to
[c. Log2 (A1)xe2x88x92r]. Log2 (A2),
xe2x80x83where:
c is the number of cyclotomic classes where there exist roots of the code over the second alphabet, and
r is the number of such roots,
and determining redundant symbols capable of allowing decoding of the code words formed from primary symbols and redundant symbols, by a decoder (20) working on the second alphabet said step having an operation of solving a system of equations expressing the constraints to be met so that the said redundant symbols are in the first alphabet, and
a step of outputting the symbols of the code words.
By virtue of these provisions, by solving the system of equations expressing the constraints that the symbols to be coded and the redundant symbols are all in the first alphabet, the redundant symbols are determined without having to follow an empirical testing and checking procedure.
Since the transmission of the code words uses a channel making use of the symbols of the first alphabet, and the decoding of the code words uses symbols of the second alphabet including the first alphabet, no labelling of the symbols of the first alphabet in the second alphabet is necessary.
According to a fifth aspect, the present invention relates to a decoding device, characterised in that it has:
an input of symbols of a first alphabet used on a transmission channel, and
a decoding means adapted to decode symbols of a second alphabet containing the first alphabet, the cardinal of the second alphabet being strictly greater than that of the first alphabet and not being an integer power of the cardinal of the first alphabet, the symbols of the second alphabet being, at the input of the decoding means, composed of the juxtaposition of symbols of the first alphabet and predetermined symbols.
Correlatively, according to a sixth aspect, the present invention relates to a decoding method, characterised in that it has:
a step of inputting symbols of a first alphabet used on a transmission channel, and
a decoding step, during which symbols of a second alphabet containing the first alphabet are decoded, the cardinal of the second alphabet being strictly greater than that of the first alphabet and not being an integer power of the cardinal of the first alphabet, the symbols of the second alphabet decoded during the decoding step being composed of the juxtaposition of symbols of the first alphabet and predetermined symbols.
The present invention also relates to a sending system, characterised in that it has a coding device as briefly disclosed above and a means of sending a signal modulating the said physical quantity representing symbols of the code words generated by the said coding device.
The present invention also relates to a computer and a capture device having a sensor, characterised in that it has a coding device as briefly disclosed above.
The present invention also relates to a receiving system, characterised in that it has a decoding device as briefly explained above and a means of receiving signals from the transmission channel.
The present invention also relates to an information storage means which can be read by a computer or a microprocessor, storing instructions of a computer program characterised in that it enables the coding method as briefly disclosed above.
The present invention also relates to an information storage means which can be read by a computer or a microprocessor, storing instructions of a computer program characterised in that it enables the decoding method as briefly disclosed above.
Since the advantages of the decoding device and method and of the sending systems, computer, capture device and receiving system are the same as those of the coding device, these advantages are not repeated here.